package leetcode_top;
import java.util.*;
import org.junit.*;

public class Ex395 {
    class SolutionX {
        public int longestSubstring(String s, int k) {
            int[] nums = new int[26];
            char[] cs = s.toCharArray();
            int len = cs.length;
            for (int i = 0; i < len; i++) {
                nums[cs[i] - 'a']++;
            }
            int lo = 0, hi = 0, max = 0;

            while (lo < len) {
                while (lo < len && nums[cs[lo] - 'a'] < k) {
                    lo++;
                }
                hi = lo;
                while (hi < len && nums[cs[hi] - 'a'] >= k) {
                    hi++;
                }
                max = Math.max(max, hi - lo);
                lo = hi;
            }
            return max;
        }
    }

    class Solution {
        public int longestSubstring(String s, int k) {
            int[] nums = new int[26];
            char[] cs = s.toCharArray();
            int len = cs.length;
            for (int i = 0; i < len; i++) {
                nums[cs[i] - 'a']++;
            }
            int lo = 0, hi = 0, max = 0;
            while (lo < len) {
                Map<Character, Integer> map = new HashMap<>();
                while (lo < len && nums[cs[lo] - 'a'] < k) {
                    lo++;
                }
                hi = lo;
                while (hi < len && nums[cs[hi] - 'a'] >= k) {
                    map.put(cs[lo], map.getOrDefault(cs[lo], k) - 1);
                    if (map.size() == 0) {
                        max = Math.max(max, hi - lo + 1);
                    }
                    hi++;
                }
                lo = hi;
            }
            return max;
        }
    }

    static class Solution2 {
        public static int longestSubstring(String s, int k) {
            char[] str = s.toCharArray();
            int allKinds = 26; // 尝试26种情况
            int ans = 0;
            for (int kinds = 1; kinds <= allKinds; kinds++) { // 尝试26种情况，每种收集一个答案，取max
                ans = Math.max(ans, maxLenOnKinds(str, k, kinds));
            }
            return ans;
        }
    
        // 求当字符种类严格等于kinds种时，每个字符出现次数>=k的最长子串的长度
        private static int maxLenOnKinds(char[] s, int k, int kinds) {
            int n = s.length;
            int[] charCountMap = new int[26]; // 字符词频表
            int curKinds = 0; // 当前窗口内的字符种类数
            int kindsOfReach = 0; // 当前窗口内达标的字符种类数
            int l = 0, r = 0; // 窗口左右边界
            int ans = 0;
            for (l = 0; l < n; l++) { // 依次固定每个位置做左端点，尝试向右最远能扩到哪里
                // 窗口右边界不断向右扩，直到右边界字符再进来后会使得窗口内种类中>kinds停，或者越界停
                while (r < n && !(curKinds == kinds && charCountMap[s[r] - 'a'] == 0)) {
                    charCountMap[s[r] - 'a']++;
                    if (charCountMap[s[r] - 'a'] == 1) curKinds++; // 窗口内新增一种字符
                    if (charCountMap[s[r] - 'a'] == k) kindsOfReach++; // 窗口内新增一种达标字符
                    r++;
                }
                if (kindsOfReach == kinds) { // 扩不动了，如果此时窗口内字符种类全部达标，则收集答案
                    ans = Math.max(ans, r - l);
                }
                if (r == n) break; // 小优化，窗口右边界越界可以直接退出了，无需再做无用功
                // 窗口左边界开始向右缩进，左边界字符出窗口：
                if (charCountMap[s[l] - 'a'] == 1) curKinds--; // 窗口内减少一种字符
                if (charCountMap[s[l] - 'a'] == k) kindsOfReach--; // 窗口内减少一种达标字符
                charCountMap[s[l] - 'a']--;
            }
            return ans;
        }
    }


    class Solution1X {
        int[] nums = new int[26];
        public int longestSubstring(String s, int k) {
            char[] cs = s.toCharArray();
            int len = cs.length;
            for (int i = 0; i < len; i++) {
                nums[cs[i] - 'a']++;
            }
            return recur(s, k);
        }

        public int recur(String s, int k) {
            int len = s.length();
            if (len < k) return 0;
            char c;
            String[] strs;
            int max = 0;
            boolean flag = true;
            for (int i = 0; i < len; i++) {
                c = s.charAt(i);
                if (nums[c - 'a'] < k) {
                    strs = s.split(String.valueOf(c));
                    flag = false;
                    for (int j = 0; j < strs.length; j++) {
                        max = Math.max(max, recur(strs[j], k));
                    }
                }
            }
            return flag ? len : max;
        }
    }

    class Solution1 {
        public int longestSubstring(String s, int k) {
            int len = s.length();
            if (len < k) return 0;
            int[] nums = new int[26];
            char[] cs = s.toCharArray();
            for (int i = 0; i < cs.length; i++) {
                nums[cs[i] - 'a']++;
            }
            char c;
            String[] strs;
            int max = 0;
            boolean flag = true;
            for (int i = 0; i < len; i++) {
                c = cs[i];
                if (nums[c - 'a'] < k) {
                    strs = s.split(String.valueOf(c));
                    flag = false;
                    for (int j = 0; j < strs.length; j++) {
                        max = Math.max(max, longestSubstring(strs[j], k));
                    }
                }
            }
            return flag ? len : max;
        }
    }


    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(s.longestSubstring("aaabb", 3));
    }

    
    @Test
    public void test1() {
        Solution1 s = new Solution1();
        System.out.println(s.longestSubstring("aaeabbdd", 2));
    }
}
